From 015de90a18f23ef227ec38a526632ed7a77aedf1 Mon Sep 17 00:00:00 2001 From: Alex Crichton Date: Sun, 22 Nov 2015 21:18:59 -0800 Subject: [PATCH] Clean up the `cargo update` implementation a bit I've noticed some slightly odd output from `cargo update` in the past and I believe this cleanup should address what's going on under the hood. There were a few minor issues with the previous implementation. * When adding the previous graph to the list of changes, packages with multiple versions would override one another instead of all get added to one list. * The `Ord` implementation for `SourceId` was actually incorrect in that it disagreed with the `Eq` implementation. This could end up causing subtle bugs here and there. dependening on what operators were used. This tweak fixes both points and I believe should touch up the odd output I've been seeing from `cargo update`. --- src/cargo/core/source.rs | 37 +++++++--- src/cargo/ops/cargo_generate_lockfile.rs | 90 ++++++++++++++---------- 2 files changed, 79 insertions(+), 48 deletions(-) diff --git a/src/cargo/core/source.rs b/src/cargo/core/source.rs index 02f30533b..fc5765287 100644 --- a/src/cargo/core/source.rs +++ b/src/cargo/core/source.rs @@ -253,17 +253,7 @@ impl PartialOrd for SourceId { impl Ord for SourceId { fn cmp(&self, other: &SourceId) -> Ordering { - match self.inner.kind.cmp(&other.inner.kind) { - Ordering::Equal => {} - ord => return ord, - } - if let Kind::Git(..) = self.inner.kind { - match self.inner.precise.cmp(&other.inner.precise) { - Ordering::Equal => {} - ord => return ord, - } - } - self.inner.url.cmp(&other.inner.url) + self.inner.cmp(&other.inner) } } @@ -324,6 +314,31 @@ impl PartialEq for SourceIdInner { } } +impl PartialOrd for SourceIdInner { + fn partial_cmp(&self, other: &SourceIdInner) -> Option { + Some(self.cmp(other)) + } +} + +impl Ord for SourceIdInner { + fn cmp(&self, other: &SourceIdInner) -> Ordering { + match self.kind.cmp(&other.kind) { + Ordering::Equal => {} + ord => return ord, + } + match self.url.cmp(&other.url) { + Ordering::Equal => {} + ord => return ord, + } + match (&self.kind, &other.kind) { + (&Kind::Git(ref ref1), &Kind::Git(ref ref2)) => { + (ref1, &self.canonical_url).cmp(&(ref2, &other.canonical_url)) + } + _ => self.kind.cmp(&other.kind) + } + } +} + impl hash::Hash for SourceId { fn hash(&self, into: &mut S) { self.inner.kind.hash(into); diff --git a/src/cargo/ops/cargo_generate_lockfile.rs b/src/cargo/ops/cargo_generate_lockfile.rs index cd876d8d5..f120a395f 100644 --- a/src/cargo/ops/cargo_generate_lockfile.rs +++ b/src/cargo/ops/cargo_generate_lockfile.rs @@ -1,4 +1,4 @@ -use std::collections::{HashMap, HashSet}; +use std::collections::{BTreeMap, HashSet}; use std::path::Path; use core::PackageId; @@ -87,17 +87,14 @@ pub fn update_lockfile(manifest_path: &Path, }; for (removed, added) in compare_dependency_graphs(&previous_resolve, &resolve) { if removed.len() == 1 && added.len() == 1 { - if removed[0].source_id().is_git() { - try!(print_change("Updating", format!("{} -> #{}", - removed[0], - &added[0].source_id().precise().unwrap()[..8]))); + let msg = if removed[0].source_id().is_git() { + format!("{} -> #{}", removed[0], + &added[0].source_id().precise().unwrap()[..8]) } else { - try!(print_change("Updating", format!("{} -> v{}", - removed[0], - added[0].version()))); - } - } - else { + format!("{} -> v{}", removed[0], added[0].version()) + }; + try!(print_change("Updating", msg)); + } else { for package in removed.iter() { try!(print_change("Removing", format!("{}", package))); } @@ -113,57 +110,76 @@ pub fn update_lockfile(manifest_path: &Path, fn fill_with_deps<'a>(resolve: &'a Resolve, dep: &'a PackageId, set: &mut HashSet<&'a PackageId>, visited: &mut HashSet<&'a PackageId>) { - if !visited.insert(dep) { return } + if !visited.insert(dep) { + return + } set.insert(dep); - match resolve.deps(dep) { - Some(deps) => { - for dep in deps { - fill_with_deps(resolve, dep, set, visited); - } + if let Some(deps) = resolve.deps(dep) { + for dep in deps { + fill_with_deps(resolve, dep, set, visited); } - None => {} } } fn compare_dependency_graphs<'a>(previous_resolve: &'a Resolve, resolve: &'a Resolve) -> Vec<(Vec<&'a PackageId>, Vec<&'a PackageId>)> { - // Map (package name, package source) to (removed versions, added versions). - fn changes_key<'a>(dep: &'a PackageId) -> (&'a str, &'a SourceId) { + fn key(dep: &PackageId) -> (&str, &SourceId) { (dep.name(), dep.source_id()) } - fn vec_subtract(a: &[T], b: &[T]) -> Vec - where T: Ord + Clone { - let mut result = a.to_owned(); - let mut b = b.to_owned(); - b.sort(); - result.retain(|x| b.binary_search(x).is_err()); - result + // Removes all package ids in `b` from `a`. Note that this is somewhat + // more complicated because the equality for source ids does not take + // precise versions into account (e.g. git shas), but we want to take + // that into account here. + fn vec_subtract<'a>(a: &[&'a PackageId], + b: &[&'a PackageId]) -> Vec<&'a PackageId> { + a.iter().filter(|a| { + // If this package id is not found in `b`, then it's definitely + // in the subtracted set + let i = match b.binary_search(a) { + Ok(i) => i, + Err(..) => return true, + }; + + // If we've found `a` in `b`, then we iterate over all instances + // (we know `b` is sorted) and see if they all have different + // precise versions. If so, then `a` isn't actually in `b` so + // we'll let it through. + // + // Note that we only check this for non-registry sources, + // however, as registries countain enough version information in + // the package id to disambiguate + if a.source_id().is_registry() { + return false + } + b[i..].iter().take_while(|b| a == b).all(|b| { + a.source_id().precise() != b.source_id().precise() + }) + }).cloned().collect() } - let mut changes = HashMap::new(); - + // Map (package name, package source) to (removed versions, added versions). + let mut changes = BTreeMap::new(); + let empty = (Vec::new(), Vec::new()); for dep in previous_resolve.iter() { - changes.insert(changes_key(dep), (vec![dep], vec![])); + changes.entry(key(dep)).or_insert(empty.clone()).0.push(dep); } for dep in resolve.iter() { - let (_, ref mut added) = *changes.entry(changes_key(dep)) - .or_insert_with(|| (vec![], vec![])); - added.push(dep); + changes.entry(key(dep)).or_insert(empty.clone()).1.push(dep); } for (_, v) in changes.iter_mut() { let (ref mut old, ref mut new) = *v; + old.sort(); + new.sort(); let removed = vec_subtract(old, new); let added = vec_subtract(new, old); *old = removed; *new = added; } + debug!("{:#?}", changes); - // Sort the packages by their names. - let mut packages: Vec<_> = changes.keys().map(|x| *x).collect(); - packages.sort(); - packages.iter().map(|k| changes[k].clone()).collect() + changes.into_iter().map(|(_, v)| v).collect() } } -- 2.30.2